public class QuickSort {
    public static void main(String[] args) {

        int[] arr={6,1,2,7,9,3,4,5,10,8};
        quickSort(arr,0,arr.length-1);

        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }

    public static void quickSort(int[] arr,int i,int j){
        //定义两个变量要查找的范围
        int start=i;
        int end=j;
        if(start>end){
            return;//出口
        }

        //记录基准数
        int baseNumber=arr[i];

        //找到要交换的数字
        while (start!=end){
            //一定要先移end
            while (true){
                if(end<=start||arr[end]<baseNumber){
                    break;
                }
                end--;
            }
            while (true){
                if(end<=start||arr[start]>baseNumber){
                    break;
                }
                start++;
            }
            //交换start和end的元素
            int t=arr[start];
            arr[start]=arr[end];
            arr[end]=t;
        }

        int t=arr[i];
        arr[i]=arr[start];
        arr[start]=t;

        //对左边范围重做
        quickSort(arr,i,start-1);
        //对右边范围重做
        quickSort(arr,start+1,j);

    }


}
